An octree is a useful data structure that is used in many applications. These applications include spatial indexing, view frustrum culling, and surface reconstruction. In general, an octree is a three-dimensional (3-D) tree data structure. An octree is the 3-D analog of the quadtree data structure. More specifically, each internal node of the 3-D tree contains up to eight children.
An octree is a hierarchical data structure that is frequently used to completely partition a 3-D space. This partitioning is performed by recursively subdividing the 3-D space into eight equal pieces, or octants. Each node in the octree is recursively subdivided such that the space represented by each node is in one of the eight octants.
As mentioned above, an octree can be used in surface reconstruction. In surface reconstruction, the octree is used to perform surface reconstruction from point clouds. Traditionally, the octree is built from the point clouds using a central processing unit (CPU). Using a CPU to build an octree is the standard way an octree is built for use in surface reconstruction.
In theory, creating an octree from point clouds directly on a graphics processing unit (GPU) is highly desirable because of the parallel processing power of the GPU. In practice, however, creating the octree directly on a GPU is quite difficult. This difficulty is due in part to the problems of memory allocation and pointer creation. Some existing techniques use both a CPU and a GPU to create an octree. These techniques use an abstract and generic template library to define complex, random-access GPU data structures, such as octrees. One problem, however, with these techniques is that the octree is not constructed exclusively on the GPU. In particular, these techniques first construct the octree on central processing unit (CPU) and then send the octree to the GPU for use.
At least one existing technique builds a probability octree entirely on a GPU. This probability octree is a specialized type of octree that can only be used for specific, limited applications. The probability octree is built on the GPU to support adaptive clustering. The probability octree, however, is not a complete octree data structure. In particular, a complete octree data structure forms a complete partition of a 3-D space, and contains node, vertex, edge, and face arrays, and contains neighborhood information about neighboring nodes of the octree nodes.
On the other hand, the probability octree does not form a complete partitioning of a 3-D space (or volume) and only contains node information. Other elements such as faces, edges, and the neighborhood information are missing. The probability octree does not match a traditional, complete octree definition or have all the properties of the complete octree. In particular, a complete octree provides information about vertices, edges and faces of octree nodes, as well as the links to all neighbors of each octree node. This information, which is necessary for GPU surface reconstruction, is missing from a probability octree. Such probability octrees are not suitable for use in surface reconstruction.